﻿//https://leetcode.cn/problems/advantage-shuffle/

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2)
    {
        int n = nums1.size();
        vector<int> ret(n);
        vector<int> index2(n);
        //排序
        sort(nums1.begin(), nums1.end());
        for (int i = 0; i < n; i++) index2[i] = i;
        sort(index2.begin(), index2.end(), [&](int i, int j)
            {
                return nums2[i] < nums2[j];
            });

        //田忌赛马
        int left = 0, right = n - 1;
        for (int i = 0; i < n; i++)
        {
            if (nums1[i] > nums2[index2[left]]) ret[index2[left++]] = nums1[i];
            else ret[index2[right--]] = nums1[i];
        }

        return ret;
    }
};